#include <iostream>
#include <cstdio>
#include <cstdlib>

#include <assert.h>

#ifdef _OMP
#include <omp.h>
#endif

#include "Utils.h"
#include "Kadane.h"


void Kadane::kadane_optimized(const Data& data, vector<Result>& vResult)
{
	const Mat & a = data.getMat();
	//const t_int* Mat = &(data.getMat()[0][0]);
	//const t_int *V = &(data.getVect()[0]);

	int M = data.getM();
	int N = data.getN();

	Result result;
	result.sum = - 1 >> 31;

	vResult.push_back(result);

#pragma omp parallel
        {
	Result my_result;
	my_result.sum = - 1 >> 31;
	//t_int pr[N];
	t_int *pr = (t_int *) malloc(N * sizeof (t_int));

#pragma omp for schedule(static, 10)
	for(int z = 0; z < M; z ++)
	{
		for(int i = 0; i < N; i++)
		{
			pr[i] = 0;
		}

		for(int x = z; x < M; x ++)
		{
			const t_int *pA = &(a[x][0]);
			int s = - 1 >> 31;
			int t = 0;
                        int j = 0;
                        int k = 0;
                        int l = 0;

			t_int *ppr = &(pr[0]);

			for(int i = 0; i < N; i ++)
			{
				*ppr += (*pA);
				//pr[i] += (*pA);
				pA ++;
				//pr[i] = pr[i] + a[x][i];

				t += *ppr;
				//t += pr[i];

				ppr ++;

				if(t > s)
				{
				    s = t;
				    k = i;
				    l = j;
				}

				if(t < 0)
				{
				    t = 0;
				    j = i + 1;
				}
			}

			if(s > my_result.sum)
			{
				my_result.sum = s;
				my_result.y1 = x;
				my_result.x1 = k;
				my_result.y0 = z;
				my_result.x0 = l;
			}
		}
	}

#pragma omp critical
        {

		#if ALL_ANSWERS
		if (my_result.sum >= vResult[0].sum)
		{
			//if (my_result.sum == vResult[0].sum)
			//	my_result.display();
			if (my_result.sum > vResult[0].sum)
				vResult.clear();

			vResult.push_back(my_result);
		}

		#else

		if (my_result.sum > vResult[0].sum)
			vResult[0] = my_result;
		#endif
        }

        free(pr);
        } //omp parallel
}



void Kadane::kadane2D(const Data& data, Result& result, const int num_threads)
{
	const Mat & a = data.getMat();
	//const t_int* Mat = &(data.getMat()[0][0]);

	int M = data.getM();
	int N = data.getN();
        result.sum = - 1 >> 31;
        int chunk_size = M / (num_threads * CHUNK_FACTOR);
        cout << "chunk = " << chunk_size << endl;

#pragma omp parallel
        {
            Result my_result;
            my_result.sum = - 1 >> 31;
            int pr[N];

#pragma omp for schedule(static, 10)
	for(int z = 0; z < M; z ++)
	{
	//	#pragma omp parallel for schedule(static, chunk)
		for(int i = 0; i < N; i++)
			pr[i] = 0;

		for(int x = z; x < M; x ++)
		{
			//const t_int *pA = &(a[x][0]);
			int s = - 1 >> 31;
			int t = 0;
                        int j = 0;
                        int k = 0;
                        int l = 0;

			for(int i = 0; i < N; i ++)
			{
				//pr[i] = pr[i] + (*pA);
				//pA ++;
				pr[i] = pr[i] + a[x][i];
				t = t + pr[i];
				if(t > s)
				{
				    s = t;
				    k = i;
				    l = j;
				}

				if(t < 0)
				{
				    t = 0;
				    j = i + 1;
				}
			}

			if(s > my_result.sum)
			{
				my_result.sum = s;
				my_result.y1 = x;
				my_result.x1 = k;
				my_result.y0 = z;
				my_result.x0 = l;
			}
		}
	}

#pragma omp critical
        {
            if (my_result > result)
                result = my_result;
        }
        }//omp parallel
}


void Kadane::kadane2DVect(const Data& data, Result& result)
{
	//const Vect & V = data.getVect();

	const t_int *V = &(data.getVect()[0]);

	int M = data.getM();
	int N = data.getN();
        result.sum = 1 << 31;
#pragma omp parallel
        {
	Result my_result;
	my_result.sum = 1 << 31;
	int pr[N];


#pragma omp for
	for(int z = 0; z < M; z ++)
	{
		for(int i = 0; i < N; i++)
			pr[i] = 0;

		for(int x = z; x < M; x++)
		{
			const t_int *pA = V + x * N;
			int s = 1 << 31;
			int t = 0;
                        int j = 0;
                        int k = 0;
                        int l = 0;

			for(int i = 0; i < N; i++)
			{
				pr[i] = pr[i] + (*pA);
				pA ++;
//				pr[i] = pr[i] + V[x * N + i];
				t = t + pr[i];
				if(t > s)
				{
				    s = t;
				    k = i;
				    l = j;
				}

				if(t < 0)
				{
				    t = 0;
				    j = i + 1;
				}
			}

			if(s > my_result.sum)
			{
				my_result.sum = s;
				my_result.y1 = x;
				my_result.x1 = k;
				my_result.y0 = z;
				my_result.x0 = l;

			}
		}
	}
#pragma omp critical
        {
            if (my_result > result)
                result = my_result;
        }
        }//pragma omp parallel
}

void Kadane::kadane2DBlock(const Data& data, Result& result, const s_rect rSubBlock)
{
	const Mat & a = data.getMat();
	//cout << "Kadane2DBlock on " << rSubBlock.x0 << "," << rSubBlock.y0 << " to " << rSubBlock.x1 << "," << rSubBlock.y1 << endl;
//	Des assertions si jamais l'utilisateur a du mal
	assert(rSubBlock.x1 >= rSubBlock.x0);
	assert(rSubBlock.y1 >= rSubBlock.y0);
	assert(rSubBlock.x1 <= (t_int) data.getN());
	assert(rSubBlock.y1 <= (t_int) data.getM());

	int size = ABS(rSubBlock.x1 - rSubBlock.x0) + 1;
	//int chunk = ABS(rSubBlock.y1 - rSubBlock.y0)/2;

        result.sum = - 1 << 31;

#pragma omp parallel
        {
	Result my_result;
	my_result.sum = - 1 << 31;
	int pr[size];

#pragma omp for schedule(static,20)
	for(int z = rSubBlock.y0; z <= rSubBlock.y1; z ++)
	{
		for(int i = 0; i < size; i++)
			pr[i] = 0;

		for(int x = z; x <= rSubBlock.y1; x ++)
		{
			int s = - 1 << 31;
			int t = 0; int j = rSubBlock.x0; int  k = 0; int l = rSubBlock.x0;
			int pr_index = 0;

			for(int i = rSubBlock.x0; i <= rSubBlock.x1; i++)
			{
				pr[pr_index] = pr[pr_index] + a[x][i];
				t = t + pr[pr_index];
				if(t > s)
				{
				    s = t;
				    k = i;
				    l = j;
				}

				if(t < 0)
				{
				    t = 0;
				    j = i + 1;
				}
				pr_index++;
			}

			if(s > my_result.sum)
			{
				my_result.sum = s;
				my_result.y1 = x;
				my_result.x1 = k;
				my_result.y0 = z;
				my_result.x0 = l;
			}
		}
	}
#pragma omp critical
	{
	if (my_result > result)
		result = my_result;
	}
	}//pragma omp parallel

}
